پیشرفت ریاضیات از ۱۹۰۰ تا ۱۹۳۹
کار بر روی ماشینهای محاسبه ادامه یافت. تعدادی ماشین محاسبه برای موارد خاص ساختهشد. برای مثال در سال ۱۹۱۹ کاریسن گروهبان فرانسوی دستگاه بسیار جالبی برای تشخیص اول بودن اعداد ساخت. لئوناردو تورس اسپانیایی هم در همین سالها چند ماشین محاسبه الکترومکانیکی ساخت، از جمله ماشینی که توانایی اتمام بازیهای سادهی شطرنج را داشت.
دیوید هیلبرت
در سال ۱۹۲۸ ریاضیدان آلمانی دیوید هیلبرت خطابهای در کنگرهی بینالمللی ریاضی ایراد کرد. وی در این سخنرانی پرسشهایی را مطرح کرد که در آینده، ریاضیات باید به آنها پاسخ بگوید. سه تا از این پرسشها تاثیر گستردهای در پیدایش علوم کامپیوتر گذاشت:
- آیا ریاضی تمامیت دارد؟ یعنی آیا میتوان هر گزارهی ریاضی را اثبات یا رد کرد؟
- آیا ریاضیات سازگار است؟ که آیا گزارهای همانند $1=0$ را نمیتوان با روشهای معتبر اثبات کرد؟
- آیا ریاضیات تصمیمپذیر است؟ یعنی آیا روشی ریاضی وجود دارد که بتوان به تمامی ادعاهای ریاضی اعمال کرد و درستی آن را سنجید؟ پرسش آخر «مسالهی تصمیم» نام گرفت.
کرت گودل
در سال ۱۹۳۱ کرت گودل به دو پرسش نخست هیلبرت پاسخ گفت. او نشان داد هر روش فرمال به اندازهی کافی توانمند، یا ناسازگار است یا ناتمام. به علاوه اگر یک سیستم اصلموضوعهای سازگار باشد، این سازگاری در خود آن قابل اثبات نیست. پرسش سوم همچنان باز ماند با جایگزینی کلمهی «اثباتپذیر» به جای کلمهی «درست».
آلن تورینگ
در سال ۱۹۳۶ آلن تورینگ با ساخت یک مدل صوری از یک کامپیوتر (معروف به ماشین تورینگ) برای مسئلهی تصمیمپذیری هیلبرت پاسخی یافت، و نشان داد که مسایلی از این رده وجود دارد که چنین ماشینی توانایی پاسخگویی به آنها را ندارد. یکی از این مسایل به مسئله هالتینگ معروف است: اگر یک برنامه پاسکال داشته باشیم، آیا این برنامه با هر ورودیای به جواب میرسد و از محاسبه میایستد؟
